№ від . .2009р. Міністерство Освіти і Науки України Національний Університет “Львівська Політехніка”
Кафедра СКС Алгоритми та методи обчислень Методичні вказівкидо лабораторних робіт з курсу “Алгоритми та методи обчислень” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” Затвердженона засіданні кафедриСпеціалізованих Комп’ютерних Систем Протокол №  від ____ 2009 року Львів – 2009  Алгоритми та методи обчислень : Методичні вказівки до лабораторних робіт з курсу “ Алгоритми та методи обчислень ” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: М. Черкаський, В. Мітьков – Львів: Національний університет “Львівська політехніка”, 2009, __ с. Укладачі: М. Черкаський, професор кафедри СКС В. Мітьков,ст.. викладач кафедри СКС Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н. Юрчак І. Ю., доцент кафедри САПР, к. т. н.  Алгоритми та методи обчислень Вступ Наукове пізнання навколишнього світу людина здійснює за допомогою його моделювання. Кожна наукова дисципліна широко використовує різні моделі. Графічні схеми, математичні рівняння, діаграми причинно-наслідкових зв'язків, таблиці і навіть вербальні конструкції є різновидами моделювання. Модель - це формалізоване, спрощене представлення реального об'єкту Будь-яка наукова модель має цільовий характер, тобто вона будується для конкретних цілей і для вирішення певних задач. Вона достатньо точно відображає ті сторони модельованого явища, які мають ключове значення для вирішення поставленої задачі. Укладена в моделі помилка рано чи пізно заважає вирішувати інші задачі, пов'язані з модельованим об'єктом. Вирішити нові задачі можна або шляхом уточнення, узагальнення первинної моделі, або шляхом побудови нової моделі. Алгоритм – фундаментальне поняття математики, йому не можна дати точне математичне визначення із залученням інших фундаментальних понять. Відсутність такого визначення не заважає інтуїтивному розумінню його змісту. Але в літературних джерелах наводяться різні варіанти розуміння сутності алгоритму. В загальному випадку під терміном “алгоритм” розуміють шлях (метод, спосіб) розв’язання задачі. Таке тлумачення не дозволяє досліджувати особливості роботи, конструювати ефективні алгоритми. Проблема розв’язується застосуванням моделей алгоритму. В залежності від складності задачі, мети дослідження, практичного застосування моделі поділяються на декілька груп, які показані на рис.1. Рис. 1 Виконанню обчислювальних операцій без вказівки на засоби виконання відповідають дві моделі: “алгоритм – процес” і “алгоритм – припис” Першу модель “алгоритм – процес” виконання чотирьох арифметичних операцій детально у словесній формі описав аль-Хорезмі (IX стор). Пізніше в працях Хр. Рудольфа (XVI стор.) і Г.В.Лейбніця (XVII стор.) модель аль-Хорезмі набула наступного тлумачення – “Алгоритм означає будь-який регулярний обчислювальний процес, який за кінцеву кількість кроків розв’язує задачі визначеного класу” [1]. Це тлумачення близьке до наведеного у сучасній фундаментальній монографії: “Кажучи неформально, алгоритм – це будь-яка коректно сформульована обчислювальна процедура, на вхід якої подається деяка величина або набір величин, і результатом виконання якої є вихідна величина або набір значень” [2]. Більш детальне тлумачення з описом властивостей алгоритму дано А Марковим: “а) Алгоритм – це процес послідовної побудови величин, який проходить в дискретному часі таким чином, що в початковий момент задається початкова скінчена система величин, а в кожний наступний момент система величин отримується за певним законом (програмою) із системи величин, які були в попередній момент часу (дискретність алгоритму). б) Система величин, які утримуються в якийсь (не початковий) момент часу, однозначно визначається системою величин, отриманих в попередні моменти часу (детермінованість алгоритму). в) Закон отримання наступної системи величин із попереднь...